package com.licw.templates.SegmentTree;


/**
 * 区间更新、区间查询、动态开点
 */
public class SegmentTree2 {

    class Node {
        int l, r;
        int val;
        int lazy;
        Node leftNode, rightNode;

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
        }


        public Node getLs() {
            if (leftNode == null) {
                leftNode = new Node(this.l, getM(l, r));
            }
            return leftNode;
        }

        public Node getRs() {
            if (rightNode == null) {
                rightNode = new Node(getM(l, r) + 1, this.r);
            }
            return rightNode;
        }

    }

    private final Node root;

    private int getM(int l, int r) {
        return (r + l) >> 1;
    }

    public SegmentTree2(int maxV) {
        root = new Node(0, maxV);
    }

    /**
     * 区间更新，更新[ul, ur]的元素
     */
    public void update(int ul, int ur, int val) {
        this.update(root, ul, ur, val);
    }

    /**
     * 查询[l, r]区间和
     */
    public int query(int ql, int qr) {
        return this.query(root, ql, qr);
    }


    /**
     * @param o 当前节点
     * @param ul   更新区间左边界
     * @param ur   更新区间右边界
     * @param val  修改（增加）值
     */
    private void update(Node o, int ul, int ur, int val) {
        if (o.l > ur || o.r < ul) return;

        if (ul <= o.l && ur >= o.r) {
            o.val += (o.r - o.l + 1) * val;
            o.lazy += val; // 标记[o.l, o.r]的值增加val
            return;
        }
        // 需要查找孩子节点，要将lazy标记向下传递
        pushDown(o);
        update(o.getLs(), ul, ur, val);
        update(o.getRs(), ul, ur, val);
        pushUp(o);//向上更新
    }

    private void pushUp(Node o) {
        o.val = o.getLs().val + o.getRs().val;
    }

    /**
     * 将lazy下推
     */
    private void pushDown(Node o) {
        if (o.l == o.r || o.lazy == 0) return;
        Node ln = o.getLs();
        Node rn = o.getRs();

        // 更新左右孩子节点的值，为lazy标记×孩子节点表示的区间长度
        ln.val += (ln.r - ln.l + 1) * o.lazy;
        rn.val += (rn.r - rn.l + 1) * o.lazy;
        // 将lazy标记向下传给左右孩子节点
        ln.lazy += o.lazy;
        rn.lazy += o.lazy;

        o.lazy = 0; // 清除该节点的lazy标记，防止重复更新
    }

    /**
     * 查询区间[qL, qR] 的结果
     *
     * @param o 当前节点
     * @param qL   查询区间左边界
     * @param qR   查询区间右边界
     */
    private int query(Node o, int qL, int qR) {
        // 如果没有交集
        if (o.l > qR || o.r < qL) return 0;

        // 如果节点区间位于查询区间之内，直接返回该区间的值
        if (qL <= o.l && qR >= o.r) {
            return o.val;
        }
        int res = 0;
        pushDown(o);

        res += query(o.getLs(), qL, qR);
        res += query(o.getRs(), qL, qR);
        return res;
    }
}